package sjjg.graph;

import java.util.HashSet;
import java.util.Stack;

public class DepthFirstPaths {
    private int s;//记录起始节点
    private int[]edgeTo;//用来表示连通节点的前一个节点
    private boolean[] marked;//用来标识某节点是否完成搜索
    DepthFirstPaths(Graph graph,int s){
         this.s=s;
         marked=new boolean[graph.V()];
         edgeTo=new int[graph.V()];
         dfp(graph,s);
    }
    //深度优先遍历非递归
    private void dfpByStack(Graph graph, int v) {
        if (graph == null) return;
        Stack<Integer> stack = new Stack<>();
        HashSet<Integer> set = new HashSet<>();
        stack.add(v);
        set.add(v);
        System.out.println(v);
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            for (Integer node : graph.adj[pop]) {
                if(!set.contains(node)){
                    System.out.println(node);
                    set.add(node);
                    stack.push(pop);
                    stack.push(node);
                    break;
                }
            }
        }
    }
    private void dfp(Graph graph,int v){
           //标识节点v已被搜索
           marked[v]=true;
           //对v的所有子节点进行深度优先遍历
        for (Integer integer : graph.adj[v]) {
            if(!marked[integer]){
                edgeTo[integer]=v;//保存到达该节点的上一个节点
                dfp(graph,integer);//递归进行深度优先遍历
            }
        }
    }
    public boolean hasPath(int v){//节点v到s是否存在路径
        return marked[v];
    }
    public Stack<Integer>pathTo(int v){//返回顶点s到节点v的路径
        if(!hasPath(v)){
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        while (v!=s){
            stack.push(v);
            v=edgeTo[v];
           }
           stack.push(s);
           return stack;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.addEdge(0,1);
        graph.addEdge(1,5);
        graph.addEdge(5,3);
        graph.addEdge(3,2);
        graph.addEdge(2,4);
        graph.addEdge(6,7);
        graph.addEdge(8,8);
        DepthFirstPaths depthFirstPaths = new DepthFirstPaths(graph, 0);
        Stack<Integer> path = depthFirstPaths.pathTo(4);
        StringBuilder pathTo=new StringBuilder();
        if(path==null){
            return;
        }
        while (!path.empty()){
            Integer pop = path.pop();
            pathTo.append(pop+"->");
        }
        pathTo.delete(pathTo.length()-2,pathTo.length());
        System.out.println(pathTo);
    }
}
